// hdu5727
// 题意：
// 给定一个二部图，每一部点数都是n(<=9)，现在找一条回路，从左到右再从到左
// 不重复的经过所有点构成一个环。现在告诉你一些边，如有两部间的点有边，
// 那么在构成的回路上左部的那个点就会变暗，现在要问最好的情况下，最少的
// 变暗的点数是多少。
//
// 题解：
// 首先，枚举右部点的排列，这样如果右部连个点到左部，左部接下来的点就确定了。
// 那么我们这么构图，左部到右部连续两个点（右部排列构成一个环），如果到
// 这两个点都没有原图的边，就在新图中连一条边，然后求一个最大匹配，
// n - 最大匹配 就是当前右部排列情况下的最小点数。
//
// 因为是环，所以只需要做(n-1)!次匈牙利就行。
//
// run: $exec < input > output
// opt: 0
// flag: -g
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

int const maxn = 12;
bool map[maxn][maxn];
int n, m;

bool bpg[2 * maxn][2 * maxn]; // bipartite-graph
int linked[2 * maxn];
bool vis[2 * maxn];

void init()
{
	std::memset(map, 0, sizeof(map));
}

bool hungarian_dfs(int u)
{
	for (int i = 1; i <= n; i++) {
		int v = n + i;
		if (vis[v] || !bpg[u][v]) continue;
		vis[v] = true;
		if (linked[v] == -1 || hungarian_dfs(linked[v])) {
			linked[v] = u;
			linked[u] = v;
			return true;
		}
	}
	return false;
}

int max_match()
{
	std::memset(linked, -1, sizeof(linked));
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		std::memset(vis, 0, sizeof(vis));
		if (hungarian_dfs(i)) ret++;
	}
	return ret;
}

int calc()
{
	if (n <= 1) return m;
	std::vector<int> yin;
	for (int i = 1; i <= n; i++) yin.push_back(i);
	int min = n;
	do {
		std::memset(bpg, 0, sizeof(bpg));
		for (int yang = 1; yang <= n; yang++) {
			for (int i = 1; i <= n; i++) {
				if (!map[yang][yin[i - 1]] && !map[yang][yin[i % n]])
					bpg[yang][yin[i - 1] + n] = bpg[yin[i - 1] + n][yang] = true;
			}
		}
		min = std::min(min, n - max_match());
	} while (std::next_permutation(yin.begin(), yin.end() - 1));
	return min;
}

int main()
{
	std::ios::sync_with_stdio(false);
	while (std::cin >> n >> m) {
		init();
		for (int i = 0, x, y; i < m; i++) {
			std::cin >> x >> y;
			map[x][y] = true;
		}

		std::cout << calc() << "\n";
	}
}

